package cn.qyd.sort;

import java.util.Arrays;

/**
 * @author 邱运铎
 * @date 2024-03-26 0:27
 */
public class QuickSort01 {
    public static void main(String[] args) {
//          int[] arr = new int[]{4,2,1,4,5,6,4};
//        int[] arr = new int[]{1,2};
        int[] arr = new int[]{4,2,1,4};
//        int[] arr = new int[]{4,2,1};
//        int[] arr = new int[]{4,2,1,5,34,6,12,4,45,13,23,18,34};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }
        int first = left;
        int last = right;
        int num = arr[left];
        while (first < last) {
            while (arr[first] <= num && first < right) {
                first++;
            }
            while (arr[last] >= num && left < last) {
                last--;
            }
//            while(first < right && arr[++first] - num <= 0);
//            while(last > left && arr[--last] - num >= 0);
            if (first < last) {
                swap(arr,first,last);
            } else {
                break;
            }

        }
        swap(arr,left,last);
        System.out.println(Arrays.toString(arr));
        quickSort(arr,left,last - 1);
        quickSort(arr,last + 1 , right);

    }

    //这里如果通过与或操作交换两个数字，在数组中千万别这么做，一旦交换的两个数据是数组中同一个下标，会让当前值为0
    public static void swap(int[] arr, int m, int n) {
        int temp = arr[n];
        arr[n] = arr[m];
        arr[m] = temp;
    }
}

